// #include <stdio.h>
// #include <stdlib.h>
// #include "windows.h"
//
// // **并查集结构**
// typedef struct {
//     int* parent; // 记录每个节点的父节点
//     int* rank;   // 记录树的秩（高度）
//     int size;    // 并查集的大小
// } DisjointSet;
//
// // **初始化并查集**
// void InitDSU(DisjointSet* dsu, int size) {
//     dsu->size = size;
//     dsu->parent = (int*)malloc(size * sizeof(int));
//     dsu->rank = (int*)malloc(size * sizeof(int));
//
//     for (int i = 0; i < size; i++) {
//         dsu->parent[i] = i; // 每个元素的父节点初始为自己
//         dsu->rank[i] = 1;   // 初始秩设为 1
//     }
// }
//
// // **查找（带路径压缩）**
// int Find(DisjointSet* dsu, int x) {
//     if (dsu->parent[x] != x) {
//         dsu->parent[x] = Find(dsu, dsu->parent[x]); // 递归查找，并路径压缩
//     }
//     return dsu->parent[x];
// }
//
// // **合并（按秩合并）**
// void Union(DisjointSet* dsu, int x, int y) {
//     int rootX = Find(dsu, x);
//     int rootY = Find(dsu, y);
//
//     if (rootX != rootY) {
//         // 按秩合并
//         if (dsu->rank[rootX] > dsu->rank[rootY]) {
//             dsu->parent[rootY] = rootX;
//         } else if (dsu->rank[rootX] < dsu->rank[rootY]) {
//             dsu->parent[rootX] = rootY;
//         } else {
//             dsu->parent[rootY] = rootX;
//             dsu->rank[rootX]++;
//         }
//     }
// }
//
// // **判断两个元素是否在同一集合**
// int isConnected(DisjointSet* dsu, int x, int y) {
//     return Find(dsu, x) == Find(dsu, y);
// }
//
// // **释放内存**
// void FreeDSU(DisjointSet* dsu) {
//     free(dsu->parent);
//     free(dsu->rank);
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     int n = 10; // 假设集合大小为 10
//     DisjointSet dsu;
//     InitDSU(&dsu, n);
//
//     // 进行一些合并操作
//     Union(&dsu, 1, 2);
//     Union(&dsu, 3, 4);
//     Union(&dsu, 2, 4); // 连接 1-2-4-3 形成一个集合
//     Union(&dsu, 5, 6);
//
//     // 测试查询
//     printf("1 和 3 是否在同一集合: %s\n", isConnected(&dsu, 1, 3) ? "是" : "否");
//     printf("1 和 5 是否在同一集合: %s\n", isConnected(&dsu, 1, 5) ? "是" : "否");
//
//     // 连接 1 和 5，使所有元素属于同一集合
//     Union(&dsu, 1, 5);
//     printf("1 和 5 是否在同一集合: %s\n", isConnected(&dsu, 1, 5) ? "是" : "否");
//
//     FreeDSU(&dsu);
//     return 0;
// }
